package pATT.profilingAlgorithm.PersonalSearcher;
import java.io.Serializable;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Vector;

import pATT.profile.ProfileComponent;
@SuppressWarnings("unchecked")
public class Tree extends ProfileComponent implements Serializable{

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	private Category	root  = null;
	private HashSet		child_trees  = null;
	private Hashtable	child_clusters  = null;
	private Tree 		parent_tree  = null;
//	private int		K = 4;

	private static int 	number_of_categories;
	private static int	number_of_instances;
	private static int 	number_of_clusters;

	//===================================================================================
	//   Operaciones con el arbol
	//===================================================================================

	public Tree(){
		root = new Category("ROOT", new TermVector());
		child_trees=new HashSet();
		child_clusters=new Hashtable();
		parent_tree = null;
	}

	private Tree(Category c, Tree p){
		root = c;
		child_trees=new HashSet();
		child_clusters=new Hashtable();
		parent_tree = p;
	}

	public Category getRoot(){
		return root;
	}

	public boolean hasChilds(){
		return !(child_trees.isEmpty());
	}

	public Tree getParent(){
		return parent_tree;
	}

	private void setParent(Tree p){
		parent_tree=p;
	}

	public synchronized Hashtable getClusters(){
		return child_clusters;
	}

	public synchronized int numberOfCategories(){
		Iterator it=child_trees.iterator();

		int count = 0;
		while(it.hasNext()){
			Tree ttree = (Tree)it.next();
			count = count + ttree.numberOfCategories();
		}
		return count + 1;
	}

	public synchronized Cluster getCluster(String c){
		if (child_clusters.get(c)!=null)
			return (Cluster)child_clusters.get(c);
		else{
			Iterator it=child_trees.iterator();

			while(it.hasNext()){
				Tree ttree = (Tree)it.next();
				Cluster cc = ttree.getCluster(c);
				if (cc!=null)
					return cc;
			}
			return null;
		}
	}

	public Tree getSubTree(String c){
		if ((root.getID()).equals(c))
			return this;
		else{
			if (child_trees.size()>0){
				Iterator it=child_trees.iterator();

				while(it.hasNext()){
					Tree ttree = (Tree)it.next();
					Tree cc = ttree.getSubTree(c);
					if (cc!=null) return cc;
				}
			}
		}
		return null;
	}

	public HashSet getSubTrees(){
		return child_trees;
	}

	
	private void addCluster(Cluster c){
		child_clusters.put(c.getID(),c);
	}

	private void addTree(Tree t){
		t.setParent(this);
		child_trees.add(t);
	}

	private void removeCluster(Cluster c){
		child_clusters.remove(c.getID());
	}

	private void removeTree(Tree tree){
		child_trees.remove(tree);
	}

	public synchronized void addClusterInstance(Instance instance) {
		clusterize(instance);
	}

	public synchronized void addSiblingInstance(Instance instance) {
		(getRoot()).addInstance(instance);
//System.out.println(instance.getID()+" into "+getRoot().getID());
		clusterize(instance);
	}

	public synchronized void addInstance(Instance instance) {
		(getRoot()).addInstance(instance);
//System.out.println(instance.getID()+" into "+getRoot().getID());

		Tree best_tree = classify(instance);
		if (best_tree==null){
			//se queda en este arbol
			Cluster best_cluster = clusterize(instance);
			double intra = best_cluster.getIntraSimilarity();

			if ((intra<=Settings.getEvaluationThreshold())){
				TermVector features = featureSelection(best_cluster.getCentroidNormalized());
				TermVector featuresall = (TermVector)features.clone();

				if (features.size()>0){
					features.subtract(getRoot().getWords());
					Category newc = new Category("CATEGORY #"+getNextClusterID(),best_cluster,features);
					Tree newt = new Tree(newc,this);
					System.out.println("--------------------------------------------------------");
					System.out.println("NEW CATEGORY:"+newt.getRoot().getWords().toString());
					System.out.println("INTRA SIMILARITY:"+intra);
					System.out.println("INSTANCIAS:"+best_cluster.size());
					System.out.println("ID:"+newc.getID());
					System.out.println("--------------------------------------------------------");

					for (Enumeration enum2 =best_cluster.getEnumeration(); enum2.hasMoreElements() ;) {
						String k = (String)enum2.nextElement();
						Instance cluster_instance = best_cluster.getInstance(k);
						newt.addClusterInstance(cluster_instance);
					}
					removeCluster(best_cluster);

					for (Enumeration enum2 =getClusters().keys(); enum2.hasMoreElements() ;) {
						String sc = (String)enum2.nextElement();
						Cluster cluster = (Cluster)getClusters().get(sc);

//						TermVector cen = cluster.getCentroidNormalized();
						HashSet temp = new HashSet();

						for (Enumeration enum1 =cluster.getEnumeration(); enum1.hasMoreElements() ;) {
							String k = (String)enum1.nextElement();
							Instance cluster_instance = cluster.getInstance(k);
							double c = newt.getRoot().classify(cluster_instance);
							if (c>-1){
								newt.addSiblingInstance(cluster_instance);
								temp.add(cluster_instance);
							}
						}

						for (Iterator i=temp.iterator(); i.hasNext(); ) {
							Instance ins = (Instance)i.next();
							cluster.removeInstance(ins);
						}
						if (cluster.isEmpty())
							removeCluster(cluster);
					}

					//check parent node
					TermVector overlap = new TermVector();
					if (!(featuresall.includeAllWords(getRoot().getWords()))){
						overlap = getRoot().getWords().overlappingWords(featuresall);
						TermVector newords = (TermVector)getRoot().getWords().clone();
						newords.subtract(overlap);
						Category newchild = new Category("CATEGORY #"+getNextCategoryID(),newords);
						Tree newtree = new Tree(newchild,this);
						getRoot().getWords().subtract(newords);
						newtree.promote(this,true);
						addTree(newtree);
					}
					addTree(newt);
					showTree();
					System.out.println("--------------------------------------------------------");
				}
			}
			else {
				if ((getParent()!=null)&&(getParent().getSubTrees().size()>1))
				getParent().checkIntersection(this);
			}
		}
		else {
			best_tree.addInstance(instance);
		}
	}

	public void addFeedback(Recommendation r, double f){
		HashSet instances = r.getSourceInstances();
		for (Iterator i=instances.iterator(); i.hasNext(); ) {
			ObjectValuePair o = (ObjectValuePair)i.next();
			Instance instance = (Instance)o.getObject();
			instance.addFeedback(f,o.getValue().doubleValue());
			if (instance.getRelevance()<0){
//				deleteInstance(instance);
//System.out.println("Remove instance!");
			}
		}
	}

	public double getTotalRelevance(){
		double sum = 0;
		if (child_clusters.size()>0) {
			for (Enumeration enum2 =getClusters().keys(); enum2.hasMoreElements() ;) {
				String sc = (String)enum2.nextElement();
				Cluster cluster = (Cluster)getClusters().get(sc);
				sum = sum + cluster.getRelevance();
			}
		}
		if (child_trees.size()>0) {
			Iterator it=child_trees.iterator();
			while(it.hasNext()){
				Tree ttree = (Tree)it.next();
				sum = sum + ttree.getTotalRelevance();
			}
		}
		return sum;
	}

	public double getRelevance(){
		return (getTotalRelevance() / getRoot().getInstancesNumber());
	}

	private TermVector featureSelection(TermVector centroid){
		TermVector c = (TermVector)centroid.clone();
		TermVector best = c.topN(1);

		Iterator ii = best.termIterator();
		String w = ii.next().toString();
		double d = best.get(w);

		TermVector features = new TermVector();
		for (Iterator i=centroid.termIterator(); i.hasNext(); ) {
			String s = i.next().toString();
			if ((centroid.get(s) > Settings.getSelectionThreshold()*d)){
					double dd = centroid.get(s) ;
				features.put(s,dd);
			}
		}
		return features;
	}

	private synchronized Tree classify(Instance instance){
		double May=0;
		Tree bestTree=null;

		Iterator it1=child_trees.iterator();
		Category ctree = null;
		Tree ttree = null;

		while(it1.hasNext()){
			ttree = (Tree)it1.next();
			ctree = ttree.getRoot();
			double dtree=ctree.classify(instance);

			if (dtree > May){
				May=dtree;
				bestTree=ttree;
			}
		}

		if (May>=0){
			return bestTree;
		}
		else
			return null;
	}

	private synchronized void checkIntersection(Tree best_tree){

		Iterator it=getSubTrees().iterator();
		boolean intersection = false;
		Tree max_tree=null;
		int max_overlap=0;

		while(it.hasNext()&&(!intersection)){
			Tree tcomp = (Tree)it.next();
			Category ccomp = tcomp.getRoot();
			if (!(ccomp.getID()).equals(best_tree.getRoot().getID())){
				TermVector overlap = best_tree.getRoot().getWords().overlappingWords(ccomp.getWords());
				if (overlap.size()>max_overlap){
					max_overlap = overlap.size();
					max_tree = tcomp;
				}
			}
		}
		if (max_overlap>0){
			Category ccomp = max_tree.getRoot();
			if ((max_overlap==ccomp.getWords().size())&&(max_overlap==best_tree.getRoot().getWords().size())){
				System.out.println("IDENTICAL");
			}
			else{
				System.out.println("Merging: "+max_tree.getRoot().getID()+" con "+best_tree.getRoot().getID());
				Category cnew = new Category(max_tree.getRoot(),best_tree.getRoot(),"CATEGORY #"+getNextCategoryID());

				Tree tnew = new Tree(cnew,this);

				removeTree(best_tree);
				removeTree(max_tree);

				tnew.addTree(best_tree);
				tnew.addTree(max_tree);

				addTree(tnew);
//chechker hermanas
				for (Enumeration enum2 =getClusters().keys(); enum2.hasMoreElements() ;) {
					String sc = (String)enum2.nextElement();
					Cluster cluster = (Cluster)getClusters().get(sc);

//					TermVector cen = cluster.getCentroidNormalized();
					HashSet temp = new HashSet();
					for (Enumeration enum1 =cluster.getEnumeration(); enum1.hasMoreElements() ;) {
						String k = (String)enum1.nextElement();
						Instance cluster_instance = cluster.getInstance(k);
						double c = tnew.getRoot().classify(cluster_instance);
						if (c>-1){
							tnew.addSiblingInstance(cluster_instance);
							temp.add(cluster_instance);
						}
					}

					for (Iterator i=temp.iterator(); i.hasNext(); ) {
						Instance ins = (Instance)i.next();
						cluster.removeInstance(ins);
					}
					if (cluster.isEmpty())
						removeCluster(cluster);
				}
			}
			showTree();
System.out.println("------------------------------------");
		}
	}

	private synchronized void promote(Tree t, boolean remove){ //compara sin las features superiores
		for (Enumeration enum2 =t.getClusters().keys(); enum2.hasMoreElements() ;) {
			String clu = (String)enum2.nextElement();
			Cluster cluster = (Cluster)t.getClusters().get(clu);
			addCluster(cluster);
			if (remove)
				getRoot().addCluster(cluster);
		}
		if (remove)
			t.clearClusters();

		Iterator it1=t.getSubTrees().iterator();
		Tree ttree = null;

		while(it1.hasNext()){
			ttree = (Tree)it1.next();
			addTree(ttree);
			if (remove)
				getRoot().addTree(ttree);
		}

		if (remove)
			t.clearTrees();
			
	}

	private synchronized Cluster clusterize(Instance i){ //compara sin las features superiores
		TermVector toRemove = new TermVector();
		toRemove.putAll(getRoot().getWords());
		Tree t = getParent();
		while (t!=null){
			toRemove.putAll(t.getRoot().getWords());
			t = t.getParent();
		}

		Hashtable clusters = getClusters();
		Cluster best_cluster = null;
		double 	best_sim = 0;
		for (Enumeration enum2 =clusters.keys(); enum2.hasMoreElements() ;) {
			Cluster cluster = (Cluster)clusters.get(enum2.nextElement());
			TermVector centroid = cluster.getCentroidNormalized();
			double sim = 0;
			try{
				sim = centroid.cosine(i.getVector(),toRemove);
			}catch (Exception ex){System.out.println(ex.toString());}
			if (sim >= Settings.getSimilarityThreshold()){
				if (sim >= best_sim){
					best_sim = sim;
					best_cluster = cluster;
				}
   			}
		}
		if (best_cluster != null){
			best_cluster.addInstance(i);
			return best_cluster;
		}
		else {
			Cluster newcluster = new Cluster("CLUSTER #"+getNextClusterID());
			newcluster.addInstance(i);
			addCluster(newcluster);
			return newcluster;
		}
	}

	public double getConfidence(Recommendation r) {

		Instance instance = r.getInstance();

		TermVector toRemove = new TermVector();
		toRemove.putAll(getRoot().getWords());
		Tree t = getParent();
		while (t!=null){
			toRemove.putAll(t.getRoot().getWords());
			t = t.getParent();
		}

		Hashtable clusters = getClusters();

		Vector v = new Vector();

		for (Enumeration enum2 =clusters.keys(); enum2.hasMoreElements() ;) {
			Cluster cluster = (Cluster)clusters.get(enum2.nextElement());
			for (Enumeration enum1 =cluster.getEnumeration(); enum1.hasMoreElements() ;) {
				String in = (String)enum1.nextElement();
				Instance cluster_instance = cluster.getInstance(in);
				double d = cluster_instance.compare(instance,toRemove);
				if ((new Double(d)).isNaN()) d=0;
				if (d>Settings.getSimilarityThreshold()){
					v.add(new ObjectValuePair(cluster_instance, new Double(d).doubleValue()));
				}
			}
		}
		QuickSort.sort(v);
/*
		ObjectValuePair o;
		int max = K;
		if (v.size()<K) max = v.size();
		if (v.size()==0) return 0;
		double sum_w = 0;
		double sum_rel = 0;
		
		for (int i = 0;i<max;i++){
			o = (ObjectValuePair)v.get(i);
			double rel = ((Instance)o.getObject()).getRelevance();
			double sim = o.getValue().doubleValue();
			double w = 1 / ((1-sim)*(1-sim));
			sum_w = sum_w + w;
			sum_rel = sum_rel + (rel * w);
			r.addSourceInstance(o);
		}

		for (int i = 0;i<max;i++){
			o = (ObjectValuePair)v.get(i);
			double sim = o.getValue().doubleValue();
			double w = 1 / ((1-sim)*(1-sim));
			double wf = w / sum_w;
			o.setValue(new Double(wf));
		}

		if (new Double(sum_rel/sum_w).isNaN())
		return 0;
		else
		return sum_rel / sum_w;
	*/
		if (v.size()>0){
			ObjectValuePair o = (ObjectValuePair)v.get(0);
//			Instance i = (Instance)o.getObject();
//			double rel = i.getRelevance();
			double sim = o.getValue().doubleValue();
			return sim;
		}
		else
			return 0;
	}

	public Category getCategory(String c){
		if ((root.getID()).equals(c))
			return root;
		else{
			if (child_trees.size()>0){
				Iterator it=child_trees.iterator();

				while(it.hasNext()){
					Tree ttree = (Tree)it.next();
					Category cc = ttree.getCategory(c);
					if (cc!=null) return cc;
				}
			}
		}
		return null;
	}

	public Tree getTreeRootAt(String c){
		if ((root.getID()).equals(c))
			return this;
		else{
			if (child_trees.size()>0){
				Iterator it=child_trees.iterator();

				while(it.hasNext()){
					Tree ttree = (Tree)it.next();
					Tree t = ttree.getTreeRootAt(c);
					if (t!=null) return t;
				}
			}
		}
		return null;
	}

	public Vector getParentsOfCategory(String c){

		Tree t = getTreeRootAt(c);
		Vector v = new Vector();

		while (!(t.getRoot().getID().equals("ROOT"))){
			v.addElement(t.getRoot());
			t = t.getParent();
		}
		return v;
	}

	public void clearTrees(){
		child_trees.clear();
	}

	public void clearClusters(){
		child_clusters.clear();
	}

	public ObjectValuePair evaluateRecommendation(Recommendation r){
		Instance instance = r.getInstance();
		Tree best_tree = classify(instance);
		if (best_tree==null){
			//se queda en este arbol
			if (getClusters().size()>0){
				return new ObjectValuePair(getRoot(),getConfidence(r));
			}
			else{
				return new ObjectValuePair(getRoot(),0);
			}
		}
		else
			return best_tree.evaluateRecommendation(r);
	}

	//-------------------------------------------------------------------------
	//               Comparacion de Perfiles
	//-------------------------------------------------------------------------


/**
* Devuelve la cantidad de categor?as que posee un perfil.
*/
public static int categoryNumber (Tree t) {
    HashSet set = t.getSubTrees();
    if (!(set.isEmpty()))
    { int a = set.size();
      Iterator v = set.iterator();
      while (v.hasNext())
      { Tree tree = (Tree)v.next();
        int result = categoryNumber(tree);
        a += result;
      }
      return a;
    }
    else
        return 0;
  }

	public static int getNextCategoryID(){
		return number_of_categories ++;
	}

	public static int getNextInstanceID(){
		return number_of_instances ++;
	}
	public static int getNextClusterID(){
		return number_of_clusters ++;
	}

	public boolean isEmpty(){
		return ((child_trees.size()==0)&&(child_clusters.size()==0));
	}

	public Category getCategoryLabel(String label){
		if ((root.getLabel()).equals(label))
			return root;
		else{
			if (child_trees.size()>0){
				Iterator it=child_trees.iterator();

				while(it.hasNext()){
					Tree ttree = (Tree)it.next();
					Category cc = ttree.getCategoryLabel(label);
					if (cc!=null) return cc;
				}
			}
		}
		return null;
	}

/*
	 public ObjectValuePair prediction(Instance instance){
		Tree best_tree = classify(instance);
		if (best_tree==null){
			TermVector toRemove = getRoot().getWords();
			Tree t = getParent();
			while (t!=null){
				toRemove.putAll(t.getRoot().getWords());
				t = t.getParent();
			}
			Hashtable clusters = getClusters();

			//setear valor de k
			//int k = 1;

			if (clusters.size()>0){
				Vector v = new Vector();

				for (Enumeration enum =clusters.keys(); enum.hasMoreElements() ;) {
					Cluster cluster = (Cluster)clusters.get(enum.nextElement());
					Vector dcluster=cluster.forcedClusterize(instance,toRemove);
					v.addAll(dcluster);
				}
				QuickSort.sort(v);
				return (ObjectValuePair)v.get(0);
			}
			else
				return null;
		}
		else
			return best_tree.prediction(instance);
	}
*/
	/**
	* Devuelve la profundidad de la categor?a dentro del arbol
	*/
	public int depth(){
		Tree p = getParent();
		int prof = 0;
		while(p != null) {
			prof++;
			p = p.getParent();
		}
		return prof;
	}

	public Vector getCategories(){
		Vector v = new Vector();
		if (!getRoot().getID().equals("ROOT"))
			v.add(getRoot());

		if (child_trees.size()>0){
			Iterator it=child_trees.iterator();
//			TermVector cats = new TermVector();
			Vector childs = null;
			while(it.hasNext()){
				Tree tree = (Tree)it.next();
				childs = tree.getCategories();
				v.addAll(childs);
			}
		}
		return v;
	}

	public String showTree(){
		int level=getLevel();
		String b = branch(level);
		String tmp = b+getRoot().getID()+":"+getRoot().getInstancesNumber()+":"+getRoot().getWords().toString();

//		System.out.println(b+getRoot().getID()+":"+getRoot().getInstancesNumber()+":"+getRoot().getWords().toString());
		if (child_trees.size()>0) {
			Iterator it=child_trees.iterator();
			while(it.hasNext()){
				Tree ttree = (Tree)it.next();
				tmp += '\n'+ttree.showTree();
			}
		}
		return tmp;
	}
	
	/**
	 * TODO by PATT
	 * */
	public String showProfile(){
		String print = "";
		int level=getLevel();
		String b = branch(level);
//		System.out.println(b+getRoot().getID()+":"+getRoot().getInstancesNumber()+":"+getRoot().getWords().toString());
		print += b+getRoot().getID()+":"+getRoot().getInstancesNumber()+":"+getRoot().getWords().toString();
		if (child_trees.size()>0) {
			Iterator it=child_trees.iterator();
			while(it.hasNext()){
				Tree ttree = (Tree)it.next();
				ttree.showProfile();
			}
		}
		return print;
	}

	@SuppressWarnings("unused")
	private String space(int level){
		String st="";
		for(int i=0;i<(5*level-5);i++){
			st=st+" ";
		}
		return st+"      ";
	}
	private String branch(int level){
		String st="";
		for(int i=0;i<(5*level-5);i++){
			st=st+" ";
		}
		return st+"------";
	}

	private int getLevel(){
		int level = 1;
		Tree t = this.getParent();
		while (t!=null){
			t = t.getParent();
			level++;
		}
		return level;
	}

	public HashSet allInstances(){

		Hashtable clusters = getClusters();
		HashSet all_instances = new HashSet();

		for (Enumeration enum2 =clusters.keys(); enum2.hasMoreElements() ;) {
			Cluster cluster = (Cluster)clusters.get(enum2.nextElement());

			for (Enumeration enum1 =cluster.getEnumeration(); enum1.hasMoreElements() ;) {
				String in = (String)enum1.nextElement();
				Instance cluster_instance = cluster.getInstance(in);
				all_instances.add(cluster_instance);
			}
		}
		return all_instances;
	}

	@Override
	public StringBuffer toText() {
		return new StringBuffer(showTree());
	}
}
